package com.muchfish.algorithm.stack;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class MonotonicityStack {

    /**
     * 给定一个数组,返回同等代表源数组中每个元素左边第一个小于自己的数的数组,构造单调递减栈,如果左边
     * 没有小于自己的返回-1
     *
     * @param src
     * @return
     */
    private int[] getLeftMinNum(int[] src) {
        // 结果数组
        int[] result = new int[src.length];
        // 单调递减栈 辅助保障src中数字的相对顺序，同时只保留比当前src[i]元素小的元素
        Deque<Integer> monotoneStack = new ArrayDeque<>();
        for (int i = 0; i < src.length; i++) {
            while (!monotoneStack.isEmpty() && src[i] <= monotoneStack.peek()) {
                //只保留比当前元素大的元素
                monotoneStack.pop();
            }
            if (!monotoneStack.isEmpty()) {
                //栈顶元素就是左边第一个小于当前元素的数
                result[i] = monotoneStack.peek();
            } else {
                //当前元素左边没有小于当前元素的数
                result[i] = -1;
            }
            //用栈存储，保障src了相对顺序
            monotoneStack.push(src[i]);
        }
        return result;
    }

    /**
     * 单调栈+哨兵
     * 哨兵：代表了一种边界情况，所以一般可以用哨兵来减少一些边界判断
     *
     * @param src
     * @return
     */
    private int[] getLeftMinNumOptimize(int[] src) {
        int[] result = new int[src.length];
        Deque<Integer> monotoneStack = new ArrayDeque<>();
        //提前加入哨兵
        monotoneStack.push(-1);
        for (int i = 0; i < src.length; i++) {
            while (src[i] <= monotoneStack.peek()) {
                monotoneStack.pop();
            }
            result[i] = monotoneStack.peek();
            monotoneStack.push(src[i]);
        }
        return result;
    }

    public int largestRectangleArea2(int[] heights) {
        //特殊判断
        if (heights == null) {
            return 0;
        } //构造一个新数组，安排好哨兵
        int[] h = new int[heights.length + 2];
        h[0] = -1;
        h[h.length - 1] = -1;
        System.arraycopy(heights, 0, h, 1, heights.length);
        Deque<Integer> stack = new ArrayDeque();
        //遍历前将左侧哨兵入栈
        stack.push(0);
        //定义最大面积
        int max = 0;
        for (int i = 1; i < h.length; i++) {
            while (h[i] < h[stack.peek()]) {
                //栈顶元素对应的高度
                int height = h[stack.pop()];
                //计算面积 (i - 1 - stack.peek()) * height
                max = Math.max(max, (i - 1 - stack.peek()) * height);
            }
            stack.push(i);
        }
        return max;
    }

    public static void main(String[] args) {
        int[] param = new int[]{6, 10, 3, 7, 4, 4, 12, 5};
        System.out.println(Arrays.toString(new MonotonicityStack().getLeftMinNum(param)));
        System.out.println(Arrays.toString(new MonotonicityStack().getLeftMinNumOptimize(param)));
        System.out.println(new MonotonicityStack().largestRectangleArea2(param));
    }
}


